public class question_05 {
}
//最长回文子串
class Solution_05 {
//    判断是否是回文串,等于去把大问题划分成小问题
    public boolean ifpalindrome(String s){
//        首先默认是回文串
        boolean result=true;
        char[] arr = s.toCharArray();
//        使用左右指针的方式
        int l=0;
        int r=arr.length-1;
        while (l<=r){
            if(arr[l]!=arr[r]){
                result=false;
            }
            l++;
            r--;
        }
        return result;
    }

    /**
     * @param arr 字符串数组，原始字符串来着
     * @param l 左边指针，向左边遍历
     * @param r 右边指针，向右遍历的
     * @return 以l和r为中心点向两边扩散所获得的最大的回文子串的最大长度
     */
    public int lenPalindrome(char arr[], int l, int r) {
        int len=arr.length;
        while (l>=0&&r<=len-1){
            if(arr[l]==arr[r]){
                l--;
                r++;
            }else {
                break;
            }
        }
        return r-l+1-2;
    }
    public String longestPalindrome(String s) {
//        版本四，采用动态规划的方法，用空间换取时间
        int len=s.length();
        char[] err  = s.toCharArray();
//        定义一个矩阵，用来存储每一个子串是否是回文串,注意是boolen矩阵，dp[i][j]表示从下标i到下标j所对应的字符串是不是回文串
//        核心思想 dp[i][j]=(s[i]==s[j])and(j-i<3or(dp[i+1][j-1]))
//        意思是首先位置i和位置J上面的字符要相等，这是前提，然后下面两种情况满足其中一种就可以了
//        j-i<3 表示他们中间只有一个或者零个字符；dp[i+1][j-1]中间包含的字符串也是回文串
        boolean arr[][]=new boolean[len][len];
//        对角线上的都是true
        for (int i = 0; i < len; i++) {
           arr[i][i]=true;
        }
        int l=0;
        int r=0;
        int maxlen=1;
//     遍历顺序：先升序遍历列，再升序遍历行
        for (int j = 1 ; j <len; j++) {
            for (int i = 0; i < j; i++) {
                if(err[i]!=err[j]){
                    arr[i][j]=false;
                }else {
//                    分情况
                    if(j-i<3){
                        arr[i][j]=true;
                        if((j-i+1)>maxlen){
                            maxlen=j-i+1;
                            l=i;
                            r=j;
                        }
//                        提前跳出防止后面数组越界,注意千万不要使用break，因为break是跳过这个程序上一层次的整个for循环
                        continue;
                    }
                    if(arr[i+1][j-1]){
                        arr[i][j]=true;
                        if((j-i+1)>maxlen){
                            maxlen=j-i+1;
                            l=i;
                            r=j;
                        }
                    }
                }
            }
        }
        return s.substring(l,r+1);

        ////        版本三：采用从中心点向两头扩散判断是否是回文数，跟版本一有点像，只不过考虑了abccba和abcdcba等各种情况
//        char[] arr = s.toCharArray();
//        int len = s.length();
//        int index=0;
//        int maxlen=1;
//        for (int i = 0; i <len-1; i++) {
//            int oneCenter=lenPalindrome(arr,i,i);
//            int twoCenter=lenPalindrome(arr,i,i+1);
//            int max=oneCenter>twoCenter?oneCenter:twoCenter;
//            if(max>maxlen){
////                数据更新
//                maxlen=max;
////                (maxlen-1)/2这个类似于距离半径
//                index=i-(maxlen-1)/2;
//            }
//        }
//        return s.substring(index,index+maxlen);

////        版本二：单独写一个判断是否是回文数的方法+遍历所有的子串+跟据如果小于当前的最大len提前break
//        这个版本是纯暴力，时间复杂度是O(n^3)，力扣上面显示超时，哭了
//        char[] arr = s.toCharArray();
//        int l=arr.length;
////        长度为一，直接返回
//        if (s.length()==1){
//            return s;
//        }
//        int index=0;
//        int max=1;
//        for (int i = 0; i <l-1; i++) {
////            设置一个头尾之间的距离量
//            int len=l-i-1;
////            减少时间复杂度
//            if(len+1<max){
//                break;
//            }
//            while (len>=1){
////                设置提前退出机制减少时间复杂度
//                if(len+1<max){
//                    break;
//                }
////                截取开始位置和结束位置对应的字符串,注意substring是前闭后开的
//                String subs=s.substring(i,i+len+1);
////                是回文字符串同时长度大于之前记录过的最大值则更新
//                if(ifpalindrome(subs)&&((len+1)>max)){
//                    index=i;
//                    max=len+1;
//                }
//                len--;
//            }
//        }
//        return s.substring(index,index+max);

//        第一版本有问题，脑子抽筋了，这个版本只能解决类似于abcdedchh回文数中间一个不同然后两头对称的情况
//        //        首先把字符串转化成char数组
//        char arr[]=s.toCharArray();
////        考虑长度是1和2的情况
//        if(s.length()==1){
//            return s;
//        }
//        if(s.length()==2){
//            if(arr[0]==arr[1]){
//                return s;
//            }else {
//                return ""+arr[0];
//            }
//        }
//
////        接下来要进行双重for循环
////        用来存储关键的索引
//        int index=0;
////        用来存储回文字符串的半径长度
//        int len=0;
//        for (int i = 1; i <arr.length-1 ; i++) {//第二个和倒数第二个进行遍历
//            int j=0;
//            while (i-j>=0&&i+j<=arr.length-1){
//                if(arr[i-j]==arr[i+j]){
//                    j++;
//                }else {//一旦有不相同退出循环
//                    break;
//                }
//            }
//            if(j>len){
////                更新半径
//                len=j;
////                更新原点
//                index=i;
//            }
//        }
////        将结果进行返回
//        char[] result=new char[(1*2*len)];
//        int j=0;
//        for (int i = index-len; i <=index+len ; i++) {
//            result[j++]=arr[i];
//        }
//        return result.toString();
    }

    public static void main(String[] args) {
        Solution_05 solution_05=new Solution_05();
        System.out.println(solution_05.longestPalindrome("aaaa"));
    }
}